#include <vector>
#include <unordered_map>


// 为什么可以直接跳到 i + 1
// 当 currentSurplus < 0 时
// 说明从当前 startIndex 出发到 i 站油量不够用
// 核心逻辑：startIndex 到 i 之间的任何站点 k 都不能作为起点
// 反证法证明：
// 假设 k 是 startIndex 和 i 之间的正确起点
// 那么从 startIndex 到 k-1 的剩余油量一定 >= 0（否则 startIndex 早被更新）
// 从 k 到 i 的剩余油量也必须 >= 0（否则 k 无法到达 i+1）
// 两者相加 startIndex 到 i 的总剩余油量应该 >= 0
// 这与 currentSurplus < 0 矛盾
// 因此 startIndex 到 i 之间没有正确起点
// 直接将起点更新为 i + 1 不会错过解
// 同时重置 currentSurplus 为 0（新起点油箱为空）
// startIndex = i + 1;
// currentSurplus = 0;

// 为什么不用再次遍历验证
// 遍历结束后通过 totalSurplus 判断最终结果
// 1. 若 totalSurplus < 0：
// 总油量 < 总消耗 无论从哪出发都无法绕环 返回 -1
// 2. 若 totalSurplus >= 0：
// 说明存在解 且 startIndex 是唯一解
// 原因：
// a. 算法保证从 startIndex 到 n-1 站的 currentSurplus 始终 >= 0
// 即从 startIndex 能顺利到达最后一站
// b. 由于 startIndex 是最后确定的起点
// 0 到 startIndex-1 站的总剩余油量一定 < 0（否则 startIndex 会更早更新）
// c. 总剩余油量 = 0到startIndex-1剩余 + startIndex到n-1剩余 >= 0
// 且 0到startIndex-1剩余 < 0
// 因此 startIndex到n-1的剩余油量绝对值一定大于前者
// 足以覆盖从 n-1 绕回 startIndex 的消耗
// 故 startIndex 能绕环一周 无需额外验证
// return totalSurplus >= 0 ? startIndex : -1;



using namespace std;
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int totalSurplus = 0;  // 总剩余油量：
        int currentSurplus = 0; // 当前起点出发的剩余油量
        int startIndex = 0;    // 候选起点

        for (int i = 0; i < n; ++i) {
            int surplus = gas[i] - cost[i]; //surplus 表示当前剩余油量
            totalSurplus += surplus;
            currentSurplus += surplus;

            // 关键贪心逻辑：如果当前剩余油量为负，说明从 startIndex 到 i 都不能作为起点
            // 直接将起点更新为 i+1，同时重置当前剩余油量（因为从 i+1 重新出发，油箱为空）
            if (currentSurplus < 0) {
                startIndex = i + 1;
                currentSurplus = 0;
            }
        }

        // 最终判断：总剩余油量 >= 0 时，startIndex 是唯一解
        return totalSurplus >= 0 ? startIndex : -1;
    }
};